#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n,vector<int>(n,0));
        func(1,matrix,0,0,n-1,n-1);
        return matrix;

    }
    void func(int n,vector<vector<int>>& matrix,int startrow,int startcol,int endrow,int endcol){
        if(startrow>endrow||startcol>endcol){
            return;
        }
        for(int i = startcol;i<=endcol;++i){
            matrix[startrow][i] = n++;
        }
        for(int i = startrow+1;i<=endrow;++i){
            matrix[i][endcol] = n++;
        }
        for(int i = endcol-1;i>=startcol&&(endrow!=startrow);--i){
            matrix[endrow][i] = n++;
        }
        for(int i = endrow-1;i>startrow&&(startcol!=endcol);--i){
            matrix[i][startcol] = n++;
        }
        func(n,matrix,startrow+1,startcol+1,endrow-1,endcol-1);
    }

};

int main(){
    Solution S;
    vector<vector<int>> T = S.generateMatrix(3);
    return 0;
}